package dynamicStudy;

/**
 *
 */
public class DynamicStudy04 {

    /**
     * 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
     *
     * 你可以对一个单词进行如下三种操作：
     *
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     *
     * 总结，最后一步有三种操作，插入、删除、替换（不操作）
     * 行代表word1再变长，列代表word2再变长。
     * @param args
     */
    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        int i = minDistance(word1, word2);
        System.out.println(i);
    }

    public static int minDistance(String word1, String word2){
        int m = word1.length();
        int n = word2.length();
        //定义数组,数组的状态为编辑到某个字母的距离
        int[][] dp = new int[m+1][n+1];
        //初始化,初始化值不好想
        int i, j;
        //初始化第一行
        for (i = 0; i <= n; i++){
            dp[0][i] = i;
        }
        //初始化第一列
        for (j = 0; j <= m; j++){
            dp[j][0] = j;
        }
        //进行循环
        for (j = 1; j <= m ; j++){
            for (i = 1; i <= n; i++){
                int left = dp[j][i-1];
                int down = dp[j-1][i];
                int left_down = dp[j-1][i-1];
                if (word1.charAt(j-1) != word2.charAt(i-1)){
                    left_down++;
                }
                dp[j][i] = Math.min(Math.min(left, down) +1, left_down);
            }
        }
        return dp[m][n];
    }
}
